package main

import "fmt"

func main() {
	var s string
	s = "the sky is blue"
	//s = "  hello world  "
	//s = "a good   example"
	v := reverseWords(s)
	fmt.Println(v)
}

// 151. 反转字符串中的单词、
// https://leetcode.cn/problems/reverse-words-in-a-string
func reverseWords(s string) string {
	sByte := []byte(s)

	// 去空格
	p := 0
	blankEnough := true
	for i := range sByte {
		if sByte[i] != ' ' || !blankEnough {
			sByte[p] = sByte[i]
			blankEnough = sByte[i] == ' '
			p++
		}
	}
	// 去掉最后一个空格
	if sByte[p-1] == ' ' {
		p--
	}
	sByte = sByte[0:p]
	n := len(sByte)

	// 先原地翻转
	reverse(sByte, 0, n-1)
	// 然后逐个单词翻转
	wStart := -1
	for i := 0; i < n; i++ {
		// 单词开始
		if sByte[i] != ' ' {
			if wStart == -1 {
				wStart = i
			}
		} else if wStart != -1 { //单词结束
			reverse(sByte, wStart, i-1)
			wStart = -1
		}
	}
	reverse(sByte, wStart, n-1)
	return string(sByte)
}

func reverse(sByte []byte, start, end int) {
	for start < end {
		sByte[start], sByte[end] = sByte[end], sByte[start]
		start++
		end--
	}
}
